package relativeSortArray;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // 思路 对于arr1中每个元素的大小 对应的就是在arr2[]中每个元素的大小
//        Map<Integer,Integer> map = new HashMap<>();
//        for (int i = 0; i < arr2.length; i++) {
//            map.put(arr2[i],i);
//        }
//        for (int i = 0; i < arr1.length; i++) {
//            for (int j = 0; j < arr1.length-i-1; j++) {
//                int value1 = map.getOrDefault(arr1[i],1000+arr1[i]);
//                int value2 = map.getOrDefault(arr1[i+1],1000+arr1[i+1]);
//                if(value1>value2){
//                    int t = arr1[i];
//                    arr1[i] = arr1[i+1];
//                    arr1[i+1] = t;
//                }
//            }
//        }
//        return arr1;

        // 计数排序
        int upper = 0;
        for (int x : arr1) {
            upper = Math.max(upper, x);
        }
        int[] frequency = new int[upper+1];
        for (int v: arr1) {
            ++frequency[v];
        }
        // 统计每个元素出现的次数
        int index = 0;
        for (int v: arr2) {
            while (frequency[v]>0){
                arr1[index++] = v;
                frequency[v]--;
            }
        }
        // 再arr2中没有出现的元素 按照升序排序
        for (int i = 0; i <= upper; i++) {
            while (frequency[i]>0){
                arr1[index++] = i;
                frequency[i]--;
            }
        }
        return arr1;
    }
}
